順序表的介紹

在了解順序表之前先給大家介紹一下什么叫做線性表：

線性表（linear list）：是n個具有相同特性的數據元素的有限序列。 線性表是一種在實際中廣泛使用的數據結構。

常見的線性表：順序表、鏈表、棧、隊列…
線性表在邏輯上是線性結構，也就說是連續的一條直線。但是在物理結構上并不一定是連續的，線性表在物理上存儲時，通常以數組和鏈式結構的形式存儲。

順序表就是線性表的一種，是邏輯地址和物理地址都是連續的。順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。在數組上完成數據的增刪查改 。
順序表接口的實現

順序表中是以數組來實現的，數據的大小是由數組的大小來決定的話每次新增和刪除數據的話數組的大小實時，會造成頻繁改變數組的大小，使用一個標志來記錄順序表的大小會更方便，不會經常改變數組大小 。
public class SeqList {
? ? private int[] elem;
? ? private int usedSize;//記錄當前順序表當中 有多少個有效的數據
? ? private static final int DEFAULT_CAPACITY = 10;
? ? public SeqList() {
? ? ? ? this.elem = new int[DEFAULT_CAPACITY];
? ? }
? ? // 打印順序表，注意：該方法并不是順序表中的方法，為了方便看測試結果給出的
? ? public void display() {
? ? }
? ? // 新增元素,默認在數據 最后新增
? ? public void add(int data) {
? ? }
? ? //判斷順序表是否滿了
? ? private boolean isFull() {
? ? }
? ? // 判定是否包含某個元素
? ? public boolean contains(int toFind) {
? ? ? ? return false;
? ? }
? ? // 查找某個元素對應的位置
? ? public int indexOf(int toFind) {
? ? ? ? return -1;
? ? }
? ? // 獲取 pos 位置的元素
? ? public int get(int pos) ?{
? ? }
? ? // 獲取順序表長度
? ? public int size() {
? ? }
? ? // 給 pos 位置的元素設為 value【更新的意思 】
? ? public void set(int pos, int value) {
? ? }
? ? //檢查pos下表是否合法
? ? private boolean checkPos(int pos){
? ? }
? ? // 在 pos 位置新增元素
? ? public void add(int pos, int data) {
? ? }
? ? private void resize() {
? ? }
? ? //刪除第一次出現的關鍵字key
? ? public void remove(int toRemove) {
? ? }
? ? //判斷順序表是否為空
? ? public Boolean isEmpty(){
? ? }
? ? // 清空順序表
? ? public void clear() {
? ? }
}

實現的第一個接口就是打印順表，其實就是對數組進行一個遍歷。

// 打印順序表，注意：該方法并不是順序表中的方法，為了方便看測試結果給出的
public void display() {
? ? for (int i = 0; i < this.usedSize; i++) {
? ? ? ? System.out.print(this.elem[i] + " ");
? ? }
? ? System.out.println();
}

進行新增數據的測試 ：

public static void main(String[] args) {
? ? SeqList seqList = new SeqList();
? ? seqList.add(1);
? ? seqList.add(2);
? ? seqList.add(3);
? ? seqList.add(4);
? ? seqList.add(5);
? ? seqList.add(6);
? ? seqList.add(1);
? ? seqList.add(2);
? ? seqList.add(3);
? ? seqList.add(4);
? ? seqList.add(5);
? ? seqList.add(6);
? ? seqList.display();
? ? System.out.println(seqList.contains(1));//包含1
? ? System.out.println(seqList.contains(100));//不包含100
? ? System.out.println(seqList.indexOf(4));//由元素4的下標
? ? System.out.println(seqList.indexOf(50));//沒有元素50
}

最后輸出結果：

1 2 3 4 5 6 1 2 3 4 5 6
true
false
3
-1